package com.gaogzhen.introductiontoalgorithms3.divideconquer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author gaogzhen
 * @date 2024/5/23 21:05
 */
public class MaxSubarrayIterative {

    public static Map<String, Integer> maxSubarrayIterative(int[] arr) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;
        int sum = Integer.MIN_VALUE;

        int low =0;
        int high = 0;

        int currentLow = 0;
        int currentHigh = 0;
        for (int i = 0; i < n; i++) {
            currentHigh = i;
            if (sum > 0) {
                sum += arr[i];
            } else {
                currentLow = i;
                sum = arr[i];
            }

            if (sum >  maxSum) {
                maxSum = sum;
                low = currentLow;
                high = currentHigh;
            }
        }

        Map<String, Integer> ret = new HashMap<>(3);
        ret.put("low", low);
        ret.put("high", high);
        ret.put("sum", maxSum);
        return ret;
    }


    public static void main(String[] args) {
        int[] arr = {-13, -3, -25, -20, -3, -16, -23, -18, -20, -1, -12, -5, -22, -15, -4, -7};
        Map<String, Integer> map = maxSubarrayIterative(arr);
        System.out.println(map);
    }
}
